#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/18
# @Author   :Changshu
# @File     :practice_122.py
# 122. 买卖股票的最佳时机 II
# 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
#
# 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
'''贪心算法，只要今天的价格低于明天的价格，就今天买入，明天卖出
def maxProfit(prices: list) -> int:
	ans = 0
	for i in range(1,len(prices)):
		if prices[i]>prices[i-1]:
			ans+=prices[i]-prices[i-1]
	return ans
'''

'''使用动态规划
   使用dp[i][j]数组表示状态方程，即获得的最大收益，其中j=0时，表示第i天不持有股票；j=1时，表示第i天持有股票
   两种情况
   1.当天不持有股票的原因有
   		(1)昨天不持有，今天不买
   		(2)昨天持有，今天卖了
   2.当天持有股票的原因有
   		(1)昨天不持有，今天买
   		(2)昨天持有，今天不卖
	这样初始条件就为 dp[0][0]=0,dp[0][1]=-prices[0]
	结束条件就是遍历完所有数组
	而最后一天是肯定不能持有股票的，即为边界设定，这一天一定能得出最大收益
'''

def maxProfit(prices: list) -> int:
	n=len(prices)
	if n<=1:
		return 0
	#创建二维数组，注意，一定要用深拷贝
	dp=[[0 for _ in range(2)] for _ in range(n)]
	# 设定初始条件
	dp[0][0]=0
	dp[0][1]=-prices[0]
	for i in range(1,n):
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
		dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
	return dp[n-1][0]

if __name__ == '__main__':
	# ans=maxProfit([7,1,5,3,6,4])
	ans = maxProfit([1,2,3,4,5])
	print(ans)